//
//  DoubleLinkedList.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/1/22.
//

import UIKit

/// 双向链表
class Node<T: Equatable> {

    public var val: T
    public var next: Node?
    public var prev: Node?
    init(_ val: T) {
        self.val = val
        self.next = nil
        self.prev = nil
    }
    init(_ val: T, next: Node?, prev: Node?) {
        self.val = val
        self.next = next
        self.prev = prev
    }
}

extension Node : CustomStringConvertible {
    public var description: String {
        return "\(self.val)"
    }
}

class DoubleLinkedList<T: Equatable> {
    var size: Int = 0
    private var firstNode: Node<T>?
    private var lastNode: Node<T>?

    // 通过数组创建一个单项链表
    func creatList(_ array: [T]) {
        guard array.count != 0 else {
            return
        }
        let nodeArray = array.compactMap { Node($0) }
        var nextNode: Node<T> = nodeArray.first!
        firstNode = nextNode
        size = nodeArray.count
        for node in nodeArray[1..<size] {
            nextNode.next = node
            nextNode = node
        }
        var prevNode: Node<T> = nodeArray.last!
        lastNode = prevNode
        for node in nodeArray[0..<size-1].reversed() {
            prevNode.prev = node
            prevNode = node
        }
        size = nodeArray.count
    }
    
    // 添加节点
    func add(_ index: Int, value: T) {
        guard index >= 0 else {
            return
        }
        if index == size {
            let last = Node(value, next: nil, prev: lastNode)
            lastNode?.next = last
            lastNode = last
            if size == 0 {
                firstNode = last
            }
        } else if index == 0 {
            firstNode = Node(value, next: firstNode, prev: nil)
            firstNode?.next?.prev = firstNode
        } else {
            let next = nodeOfIndex(index)
            let prev = next?.prev
            let newNode = Node(value, next: next, prev: prev)
            next?.prev = newNode
            prev?.next = newNode
        }
        size += 1
    }
    // 删除节点
    func remove(_ index: Int) -> T? {
        guard index >= 0 && index < size else {
            return nil
        }
        let node = nodeOfIndex(index)
        if index == size - 1 {
            let prev = node?.prev
            prev?.next = nil
            lastNode = prev
            if size == 1 {
                firstNode = prev
            }
        } else if index == 0 {
            let next = node?.next
            next?.prev = nil
            firstNode = next
        } else {
            let next = node?.next
            let prev = node?.prev
            prev?.next = next
            next?.prev = prev
        }
        node?.prev = nil
        node?.next = nil
        size -= 1
        return node?.val
    }
    // 修改节点
    func setNode(_ index: Int, value: T) -> T? {
        let node = nodeOfIndex(index)
        let temp = node?.val
        node?.val = value
        return temp
    }
    // 查询节点
    func getNode(_ index: Int) -> T? {
        let node = nodeOfIndex(index)
        return node?.val
    }
    // 获取某个节点的位置
    func indexOf(_ value: T) -> Int {
        var tempNode = firstNode
        for i in 0..<size {
            if tempNode?.val == value {
                return i
            }
            tempNode = tempNode?.next
        }
        return -1
    }
//    清空数据
    func clear() {
        size = 0
        firstNode = nil
        lastNode = nil
    }
    // 通过索引获取节点
    func nodeOfIndex(_ index: Int) -> Node<T>? {
        guard index >= 0 && index < size else {
            print("=============", index)
            return nil
        }
        if index < (size/2) {
            var temp: Node<T>? = firstNode;
            for _ in 0..<index {
                temp = temp?.next
            }
            return temp
        } else {
            var temp: Node<T>? = lastNode;
            for _ in (index+1..<size).reversed() {
                temp = temp?.prev
            }
            return temp
        }
        
    }
    
    // 打印一个双向链表
    func printList() {
        var head = firstNode
        var printArray = [String]()
        while let tempHead = head {
            printArray.append("\(tempHead.val)->")
            head = tempHead.next
        }
        printArray.append("nil")
        var printStr = ""
        printArray.forEach { printStr = printStr + $0 }
        print("next:\(printStr)")
        
        var last = lastNode
        var printArray1 = [String]()
        while let tempHead1 = last {
            printArray1.append("\(tempHead1.val)->")
            last = tempHead1.prev
        }
        printArray1.append("nil")
        var printStr1 = ""
        printArray1.forEach { printStr1 = printStr1 + $0 }
        print("prev:\(printStr1)")    }
}
